package easy

import (
	. "GoLeetcode/common"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

// 如果p,q均在root的左边，则公共祖先在左子树中;如果p,q在root的右边，则公共祖先在右子树
// 否则当前节点即为公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	result := root
	for {
		if result.Val > p.Val && result.Val > q.Val {
			result = result.Left
		} else if result.Val < p.Val && result.Val < q.Val {
			result = result.Right
		} else {
			break
		}
	}
	return result
}
